package main

import . "local/datastructure/graph/am"

/**
最短路径:迪杰斯特拉实现 (本例中使用邻接矩阵表示图)
思想: 同样是把所有顶点划分为两个结合，一个是已访问顶点，一个是未访问顶点，通过算法不断找出下一个最短路径顶点并加入到已访问顶点直至最后
简单记忆需要四步
init
scan
add
update
*/
const INF = 2<<31 - 1

func dj(G AMGraph, vo int) ([]int, []int) {
	/**
	初始化
		visited存储已访问的顶点
		D存储vo到i顶点的最短距离
		P存储i位置的前继顶点位置
	*/
	visited := make([]bool, G.NumVers)
	D := make([]int, G.NumVers)
	P := make([]int, G.NumVers)
	for i := 0; i < G.NumVers; i++ {
		D[i] = G.Arcs[vo][i]
		P[i] = -1
	}

	visited[0] = true
	k := 0
	for i := 1; i < G.NumVers; i++ { // 总共n个节点 还要找 n-1个节点，每次循环确定一个顶点，故需要n-1次循环

		/**
		scan: 找出未访问顶点集合中，距离vo最近的顶点
		*/
		min := INF
		for j := 0; j < G.NumVers; j++ {
			if !visited[j] && D[j] < min {
				k = j
				min = D[j]
			}
		}

		// add: 将上步找到的最小路径邻接顶点加入到已访问顶点集合中，记作临时节点
		visited[k] = true

		// update://比较通过临时顶点访问其邻接顶点vi的距离与原vo访问vi的距离，如果减小了距离，则更新D[j2]的路径长度
		for j2 := 0; j2 < G.NumVers; j2++ {
			if !visited[j2] && min+G.Arcs[k][j2] < D[j2] {
				D[j2] = min + G.Arcs[k][j2]
				P[j2] = k
			}
		}
	}
	return D, P
}
